#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    void dfs(string& cur, vector<string>& ans, int l, int r, int n) {
        if (cur.size() == 2 * n) {
            ans.push_back(cur);
            return;
        }

        if (l < n) {
            cur.push_back('(');
            dfs(cur, ans, l + 1, r, n);
            //cout<< cur[cur.size()-1]<<endl;
            cur.pop_back();
        }
        if (r < l) {
            cur.push_back(')');
            dfs(cur, ans, l, r + 1, n);
            cur.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string t = "";
        dfs(t, ans, 0, 0, n);
        return ans;
    }
};